package day70_1319;

/**
 * @ClassName Solution
 * @Description DFS(内存超出限制)
 * @Author clockTown
 * @Date 2021/7/18 19:33
 * @Version 1.0
 */
public class Solution {

    private boolean[] visited;

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1){
            return -1;
        }

        int[][] isConnection = new int[n][n];
        for (int[] connection : connections) {
            int x = connection[0];
            int y = connection[1];

            isConnection[x][y] = 1;
            isConnection[y][x] = 1;
        }

        visited = new boolean[n];

        int count = 0;
        for (int i = 0; i < isConnection.length; i++) {
            if (!visited[i]){
                dfs(isConnection, i);
                count++;
            }
        }

        return count - 1;
    }


    private void dfs(int[][] isConnection, int idx){
        this.visited[idx] = true;

        int[] temp = isConnection[idx];
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] == 1 && !visited[i]){
                dfs(isConnection, i);
            }
        }
    }


    public static void main(String[] args) {
        int[][] connections = {{0,1},{0,2},{3,4},{2,3}};
        System.out.println(new Solution().makeConnected(5,connections));
    }
}
